package 力扣;

import java.util.ArrayList;
import java.util.List;

/**
 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
 说明: 叶子节点是指没有子节点的节点。
 示例:
 给定如下二叉树，以及目标和 sum = 22，
  5
 / \
 4   8
 /   / \
 11  13  4
 /  \    / \
 7    2  5   1
 返回:
 [
 [5,4,11,2],
 [5,8,4,5]
 ]
 */

public class _113路径总和_II {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if( root == null ) return new ArrayList<>();
        ArrayList<List<Integer>> lists = new ArrayList<List<Integer>>();
        ArrayList<Integer> list = new ArrayList<>();
        backTrack(root,sum,list,lists);
        return lists;
    }

    private void backTrack(TreeNode root, int sum, ArrayList<Integer> list, ArrayList<List<Integer>> lists) {
        if( root == null ) return;
        list.add(root.val);
        if (root.left == null && root.right ==null && root.val == sum){
            lists.add(new ArrayList<>(list)); //不能return,因为可能还有其他情况，需要回溯,如果return了,就无法进行回溯
        }
        backTrack(root.left,sum- root.val,list,lists);
        backTrack(root.right,sum- root.val,list,lists);
        list.remove(list.size()-1);
    }

}
